package a00_LeetCode.LinkedList;

/**
 * @Author quan
 * @Description ☆☆☆☆☆合并两个有序链表
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * @Date 2023/3/19 11:32
 */
public class Num21_MergeTwoLists {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        /**
         * 方法1：基础做法
         * 边界条件：一个链表为空，则拼接后一定是那个非空链表；两个都为空，则返回Null
         * 当两个链表都不为空：创建新的虚拟节点，遍历两个链表，将较小的那个链表拼接到这个虚拟节点后
         * 当两个链表中一旦有一个链表遍历完成为null后，则将另一个链表直接拼接到虚拟节点后即可
         */
        /*//情况1：两个链表都为空:可以省略了，下面的情况2都包含了
        if(list1==null && list2==null){
            return null;
        }
        //情况2：有一个链表为null，则另一个链表就是合并后的链表
        if(list1 == null ){
           return list2;
        }
        if(list2 == null ){
            return list1;
        }
        //情况3：两个链表都不为null
        //(1)创建虚拟头结点
        ListNode dummyHead = new ListNode();
        ListNode tail = dummyHead;
        //(2)遍历两个链表，双指针——>----------这里的怎么遍历呢？自己没有写出来，不会写
        while (list1.next != null && list2.next !=null){
            if(list1.val > list2.val){
                tail.next = list2;//--------注意拼接的是整个链表，并不是链表中的单独节点，这里的tail=list要理解！感觉有点没绕过来
                tail = list2;
                list2 = list2.next;
            } else {
                tail.next = list1;
                tail = list1;
                list1 = list1.next;
            }
        }
        //(3)此时说明已经将其中一个链表遍历完，则直接将另一个链表的值全部加到合并链表中
        if(list1 == null){
            tail.next = list2;
        }
        if(list2 == null){
            tail.next = list1;
        }
        //(4)返回最终的头结点
        return dummyHead.next;
    }*/
        /**
         * 方法2：递归法
         */
        //边界条件
        //情况2：有一个链表为null，则另一个链表就是合并后的链表
        if(list1==null ){
            return list2;
        }
        if(list2==null ){
            return list1;
        }
        //递归的使用
        if(list1.val <= list2.val){
            list1.next = mergeTwoLists(list1.next,list2);//此时的list1中的第一个值是最小值，采用递归方法将List1的第一个节点后的所有节点与list2的所有节点合并
            return list1;//list1保存的就是最小值头结点
        } else {
            list2.next = mergeTwoLists(list1.next,list2);//list2中的第一个值是最小值
            return list2;
        }
    }
}
